package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 区间合并器
 * 
 * @author csy
 * @description 合并重叠的区间
 * 
 *              解题思路：
 *              1. 首先按区间的起始位置对区间进行排序
 *              2. 遍历排序后的区间：
 *              - 如果当前区间的起始位置大于前一个区间的结束位置，说明不重叠，直接添加到结果中
 *              - 如果重叠，则合并区间，更新结束位置为两个区间结束位置的最大值
 *              3. 最后将最后一个合并区间添加到结果中
 * 
 *              时间复杂度：O(nlogn)，主要是排序的时间复杂度
 *              空间复杂度：O(n)，存储结果的空间
 * 
 *              示例：
 *              输入：[[1,3],[2,6],[8,10],[15,18]]
 *              输出：[[1,6],[8,10],[15,18]]
 *              解释：区间 [1,3] 和 [2,6] 重叠，合并为 [1,6]
 */
public class IntervalMerger {

    /**
     * 合并重叠区间
     *
     * @param intervals 输入的区间数组，每个区间由两个数字表示：[start, end]
     * @return 合并后的区间数组
     */
    public static int[][] merge(int[][] intervals) {
        // 处理特殊情况
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // 按区间起始位置排序
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

        // 用于存储合并后的区间
        List<int[]> mergedIntervals = new ArrayList<>();

        // 初始化当前区间的起始和结束位置
        int currentStart = intervals[0][0];
        int currentEnd = intervals[0][1];

        // 遍历排序后的区间
        for (int i = 1; i < intervals.length; i++) {
            int nextStart = intervals[i][0];
            int nextEnd = intervals[i][1];

            // 如果当前区间与下一个区间不重叠
            if (currentEnd < nextStart) {
                // 添加当前区间到结果中
                mergedIntervals.add(new int[] { currentStart, currentEnd });
                // 更新当前区间为下一个区间
                currentStart = nextStart;
                currentEnd = nextEnd;
            } else {
                // 区间重叠，更新当前区间的结束位置
                currentEnd = Math.max(currentEnd, nextEnd);
            }
        }

        // 添加最后一个区间
        mergedIntervals.add(new int[] { currentStart, currentEnd });

        // 转换为二维数组返回
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        int[][] testIntervals = {
                { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 }
        };

        System.out.println("原始区间：");
        printIntervals(testIntervals);

        int[][] mergedResult = merge(testIntervals);

        System.out.println("\n合并后的区间：");
        printIntervals(mergedResult);
    }

    /**
     * 打印区间数组的辅助方法
     */
    private static void printIntervals(int[][] intervals) {
        for (int[] interval : intervals) {
            System.out.printf("[%d, %d] ", interval[0], interval[1]);
        }
        System.out.println();
    }
}